Interlocking Polyominoes
Sid Dhawan was one of our RSI 2011 math students. He was studying interlocking polyominoes under the mentorship of Zachary Abel.
A set of polyominoes is interlocked if no subset can be moved far away from the rest. It was known that polyominoes that are built from four or fewer squares do not interlock. The project of Dhawan and his mentor was to investigate the interlockedness of larger polyominoes. And they totally delivered.
They quickly proved that you can interlock polyominoes with eight or more squares. Then they proved that pentominoes can’t interlock. This left them with a gray area: what happens with polyominoes with six or seven squares? After drawing many beautiful pictures, they finally found the structure presented in our accompanying image. The system consists of 12 hexominoes and 5 pentominoes, and it is rigid. You cannot move a thing. That means that hexominoes can be interlocked and thus the gray area was resolved.
You can find the proofs and the details in their paper “Complexity of Interlocking Polyominoes”. As you can guess by the title, the paper also discusses complexity. The authors proved that determining interlockedness of a a system that includes hexominoes or larger polyominoes is PSPACE hard.
Share:
Neeraj Gupta:
Hey, I am 27 and I have done my Bachelors degree in Engineering from IIT-BHU, one of the top 5 engineering colleges in India. Since, I was not able to find another way to contact you, I am writing to u here. Right now I am working with SAIL. I would like to continue my career in Advanced Mathematics. I have always been good at mathematics,(my career choice was one of the outcomes) but I dont like the engineering field much. As I did not knew at the time of joining the engineering degree what I was getting into, I would like to make up for the mistake and would like to join Advanced mathematics field.Since all of my friends are engineers or doctors, I dont have anyone to guide me. This is the first Mathematicians blog I have ever encountered.
I would like you to help me if possible. you have my email id.. pls do contact me to help me.
Thanks
1 May 2012, 12:01 pm